'''
https://leetcode.cn/problems/longest-common-subsequence/description/
'''
import numpy as np


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        # dp[i,j]: 表示text1[0,i] 与 text[0,j] 有多少最长公共子串
        dp = np.zeros((m, n), dtype=np.uint16)
        dp[0,0] = text1[0] == text2[0]
        for i in range(1, m):
            dp[i, 0] = text1[i] == text2[0] or dp[i-1, 0]
        for j in range(1, n):
            dp[0, j] = text1[0] == text2[j] or dp[0, j-1]
        for i in range(1, m):
            for j in range(1, n):
                dp[i, j] =  max(1 + dp[i-1, j-1] if (text1[i] == text2[j]) else 0, dp[i, j-1], dp[i-1, j])
        return int(dp[-1][-1])

    def longestCommonSubsequence2(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        # dp[i,j]: 表示text1[0,i] 与 text[0,j] 有多少最长公共子串
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = text1[0] == text2[0]
        for i in range(1, m):
            dp[i][0] = max(text1[i] == text2[0], dp[i-1][0])
        for j in range(1, n):
            dp[0][j] = max(text1[0] == text2[j], dp[0][j-1])
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] =  max(1 + dp[i-1][j-1] if (text1[i] == text2[j]) else 0, dp[i][j-1], dp[i-1][j])
        return dp[-1][-1]

word1 = "abcde"
word2 = "ace"
print(Solution().longestCommonSubsequence(word1, word2))